import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-31
 * Time: 21:16
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class Solution {
    // 思路:
    // 栈
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 只记录值就行了, 不用再记录节点
        Stack<Integer> stack1 =new Stack<>();
        Stack<Integer> stack2 =new Stack<>();
        // 先记录第一个链表对应的数字
        ListNode cur=l1;
        while(cur!=null){
            stack1.push(cur.val);
            cur=cur.next;
        }
        // 再记录第二个链表对应的数字
        cur=l2;
        while(cur!=null){
            stack2.push(cur.val);
            cur=cur.next;
        }
        int flag=0; // 记录进位
        ListNode ans=null; // 一直记录头节点
        // (巧妙)这里只要其中 一个条件满足 就要进行 计算, 创建新的节点
        // 不用再把条件拆开, 降低了时间复杂度
        while(!stack1.isEmpty()||!stack2.isEmpty()||flag!=0){
            int x1=stack1.isEmpty()?0:stack1.pop();
            int x2=stack2.isEmpty()?0:stack2.pop();
            int sum=flag+x1+x2;
            flag=sum/10;
            // (巧妙) 相当于 链表的头插, 不用再统一放到栈中重新连接
            ListNode newNode=new ListNode(sum%10);
            newNode.next=ans;
            ans=newNode;
        }
        return ans;
    }
}
